package com.demo.java.OD401_450.OD418;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【来自异国的客人(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146258444
 */
public class OdMain {
    /**
     * 计算幸运数字出现的次数
     */
    public static int countLuckyNumbers(int k, int n, int m) {
        // 验证输入是否合法
        if (!(k >= 0 && n >= 0 && m > 1)) {
            return 0;
        }

        // 将 k 转换为 m 进制表示
        StringBuilder kInBaseM = new StringBuilder();
        while (k > 0) {
            int remainder = k % m;  // 计算当前余数
            kInBaseM.insert(0, remainder);  // 将余数插入到字符串的前面
            k /= m;  // 除以 m 继续计算
        }

        // 计算目标数字 n 在转换后的 m 进制数中的出现次数
        int count = countOccurrences(kInBaseM.toString(), String.valueOf(n));

        return count;
    }

    /**
     * 统计字符串中 target 子串的出现次数
     */
    public static int countOccurrences(String str, String target) {
        int count = 0;
        int lastIndex = 0;

        // 使用 indexOf 查找 target 在 str 中的所有出现位置
        while (lastIndex != -1) {
            lastIndex = str.indexOf(target, lastIndex);

            if (lastIndex != -1) {
                count++;  // 找到一个目标数字，计数加 1
                lastIndex += target.length();  // 移动到下一个位置继续查找
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        try {
            // 读取输入
            int k = scanner.nextInt();
            int n = scanner.nextInt();
            int m = scanner.nextInt();

            // 调用函数计算并输出结果
            int result = countLuckyNumbers(k, n, m);
            System.out.println(result);
        } catch (Exception e) {
            // 捕获异常，处理输入不合法的情况
            System.out.println(0);
        }
    }
}
